public class test {
    // leetcode.10 正则表达式匹配
    // 完全背包
    class Solution {
        public boolean isMatch(String S, String P) {
            char[] s = S.toCharArray(), p = P.toCharArray();
            int n = s.length, m = p.length;
            boolean[][] f = new boolean[n + 1][m + 1];
            f[0][0] = true;
            // 处理空字符串匹配 *
            for (int j = 1; j < m; j++) {
                if (p[j] == '*') {
                    f[0][j + 1] = f[0][j - 1];  // * 可以匹配空字符串
                }
            }
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    char c = p[j];
                    if (Character.isLowerCase(c)) {
                        f[i + 1][j + 1] = s[i] == c && f[i][j];
                    } else if (c == '.') {
                        f[i + 1][j + 1] = f[i][j];
                    } else {  // pj为*，对p[j-1]分类讨论
                        // 不选
                        if (p[j - 1] != '.' && p[j - 1] != s[i]) {
                            f[i + 1][j + 1] = f[i + 1][j - 1];
                        } else {
                            // 可以选
                            f[i + 1][j + 1] = f[i + 1][j - 1] || f[i][j + 1];
                        }
                    }
                }
            }
            return f[n][m];
        }
    }

}
